#include <string.h>
#include "hash.h"
#include "z_memory.h"

/* rehash when table gets this x full */
#define HASH_FULLTAB 2
/* grow table by this factor */
#define HASH_GROWTAB 4
/* self explenatory */
#define HASH_DEFAULT_SIZE 10

struct __hash {
    size_t nelem;
    size_t size;
    hash_iter_t **tab;
    const hash_ops_t *ops;
};

#define hindex(h, n)    ((h)%(n))

/******************************************************************************/
static void rehash(hash_t *a_this) {
    size_t i;
    int h, size;
    hash_iter_t **tab;
    hash_iter_t *p;
    hash_iter_t *q;

    size = HASH_GROWTAB * a_this->size;
    tab = z_calloc(size, sizeof(*tab));

    if (tab == 0) return;

    for (i = 0; i < a_this->size; i++) {
        for (p = a_this->tab[i]; p; p = q) {
            q = p->__next;
            h = hindex(p->__hkey, size);
            p->__next = tab[h];
            tab[h] = p;
            if (p->__next != 0) p->__next->__prev = p;
            p->__prev = 0;
        }
    }
    z_free(a_this->tab);

    a_this->tab = tab;
    a_this->size = size;
}

/******************************************************************************/
extern hash_t *hash_new(size_t a_size, const hash_ops_t *a_ops) {
    const static hash_ops_t default_ops = {
            (void *) &hash_hash_string,
            (void *) &strcmp,
            0, 0, 0, 0
    };

    hash_t *hash;
    hash_iter_t **tab;

    if (a_size == 0) a_size = HASH_DEFAULT_SIZE;

    hash = z_calloc(1, sizeof(*hash));
    tab = z_calloc(a_size, sizeof(*tab));

    if (hash == 0 || tab == 0) {
        z_free(hash);
        z_free(tab);
        return 0;
    }

    hash->nelem = 0;
    hash->size = a_size;
    hash->tab = tab;
    hash->ops = a_ops != 0 ? a_ops : &default_ops;

    return hash;
}

/******************************************************************************/
extern hash_iter_t *hash_lookup(hash_t *a_this, const void *a_key) {
    int h;
    hash_iter_t *p;

    if (a_this == 0 || a_key == 0) return 0;

    h = hindex(a_this->ops->hash(a_key), a_this->size);
    for (p = a_this->tab[h]; p != 0; p = p->__next)
        if (a_this->ops->compare(a_key, p->key) == 0) {
            return p;
        }

    return 0;
}

/******************************************************************************/
extern hash_iter_t *hash_look_add(hash_t *a_this, const void *a_key) {
    int h;
    hash_iter_t *p;

    if (a_this == 0 || a_key == 0) return 0;
    if ((p = hash_lookup(a_this, a_key)) != 0) return p;
    if ((p = z_calloc(1, sizeof(*p))) == 0) return 0;

    if (a_this->ops->key_dup != 0)
        p->key = a_this->ops->key_dup(a_key);
    else
        p->key = (void *) a_key;

    p->hash = a_this;
    p->__hkey = a_this->ops->hash(a_key);

    if (a_this->nelem > HASH_FULLTAB * a_this->size) rehash(a_this);

    h = hindex(p->__hkey, a_this->size);
    p->__next = a_this->tab[h];
    a_this->tab[h] = p;
    if (p->__next != 0) p->__next->__prev = p;

    a_this->nelem++;

    return p;
}

/******************************************************************************/
extern hash_iter_t *hash_add(hash_t *a_this, const void *a_key, void *a_data) {
    hash_iter_t *p;

    if ((p = hash_look_add(a_this, a_key)) == 0) return 0;

    if (a_this->ops->data_free != 0) a_this->ops->data_free(p->data);

    if (a_this->ops->data_dup != 0)
        p->data = a_this->ops->data_dup(a_data);
    else
        p->data = a_data;

    return p;
}

/******************************************************************************/
extern void hash_delete(hash_t *a_this) {
    hash_clear(a_this);
    z_free(a_this->tab);
    z_free(a_this);
}

/******************************************************************************/
extern void hash_clear(hash_t *a_this) {
    size_t h;
    hash_iter_t *p;
    hash_iter_t *q;

    if (a_this == 0) return;

    for (h = 0; h < a_this->size; h++) {
        for (p = a_this->tab[h]; p; p = q) {
            q = p->__next;
            if (a_this->ops->key_free) a_this->ops->key_free(p->key);
            if (a_this->ops->data_free) a_this->ops->data_free(p->data);
            z_free(p);
        }
        a_this->tab[h] = 0;
    }
    a_this->nelem = 0;
}

/******************************************************************************/
extern void hash_del(hash_t *a_this, const void *a_key) {
    int h;
    hash_iter_t *p;

    h = hindex(a_this->ops->hash(a_key), a_this->size);
    for (p = a_this->tab[h]; p != 0; p = p->__next)
        if (a_this->ops->compare(a_key, p->key) == 0) break;
    if (p == 0) return;

    hash_iter_del(p);
}

/******************************************************************************/
extern void hash_foreach(hash_t *a_this, hash_func_t a_func, void *a_data) {
    size_t h, ret;
    hash_iter_t *p;
    hash_iter_t *q;

    if (a_this == 0 || a_func == 0) return;

    for (h = 0; h < a_this->size; h++)
        for (p = a_this->tab[h]; p != 0; p = q) {
            p->__foreach = 1;
            ret = (*a_func)(p->key, p->data, a_data);
            q = p->__next;

            if (p->__foreach == 0)
                hash_iter_del(p);
            else
                p->__foreach = 0;

            if (ret != 0) return;
        }
}

/******************************************************************************/
extern unsigned int hash_get_nelem(hash_t *a_this) {
    if (a_this == 0) return 0;
    return a_this->nelem;
}

/******************************************************************************/
extern unsigned int hash_get_size(hash_t *a_this) {
    if (a_this == 0) return 0;
    return a_this->size;
}

/******************************************************************************/
extern hash_iter_t *hash_begin(hash_t *a_this) {
    size_t h;

    if (a_this == 0) return 0;
    for (h = 0; h < a_this->size; h++)
        if (a_this->tab[h])
            return a_this->tab[h];

    return 0;
}

/******************************************************************************/
extern hash_iter_t *hash_end(hash_t *a_this) {
    return 0;
}

/******************************************************************************/
extern hash_iter_t *hash_iter_next(hash_iter_t *a_this) {
    int h;
    size_t i;

    if (a_this == 0) return 0;
    if (a_this->__next != 0) return a_this->__next;

    h = hindex(a_this->__hkey, a_this->hash->size);

    for (i = h + 1; i < a_this->hash->size; i++)
        if (a_this->hash->tab[i])
            return a_this->hash->tab[i];

    return 0;
}

/******************************************************************************/
extern hash_iter_t *hash_iter_prev(hash_iter_t *a_this) {
    int h, i;
    hash_iter_t *p;

    if (a_this == 0) return 0;
    if (a_this->__prev != 0) return a_this->__prev;

    h = hindex(a_this->__hkey, a_this->hash->size);

    for (i = h - 1; i > 0; i--)
        for (p = a_this->hash->tab[i]; p; p = p->__next)
            if (p->__next == 0)
                return p;

    return 0;
}

/******************************************************************************/
extern void hash_iter_del(hash_iter_t *a_this) {
    if (a_this == 0) return;

    if (a_this->hash->ops->data_free != 0)
        a_this->hash->ops->data_free(a_this->data);
    a_this->data = 0;

    if (a_this->hash->ops->key_free != 0)
        a_this->hash->ops->key_free(a_this->key);
    a_this->key = 0;

    if (a_this->__foreach == 1) {
        a_this->__foreach = 0;
        return;
    }

    if (a_this->__next != 0) a_this->__next->__prev = a_this->__prev;
    if (a_this->__prev != 0)
        a_this->__prev->__next = a_this->__next;
    else
        a_this->hash->tab[hindex(a_this->__hkey, a_this->hash->size)] = a_this->__next;

    a_this->hash->nelem--;

    z_free(a_this);
}

/******************************************************************************/
extern unsigned int hash_hash_string(const char *a_string) {
    register unsigned int h;

    for (h = 0; *a_string != '\0'; a_string++)
        h = *a_string + 31 * h;

    return h;
}
